package 力扣.栈;


import java.util.Arrays;
import java.util.Stack;

public class 柱状图中最大的矩形84 {
    public static void main(String[] args) {
        int[] ints = {2,1,5,6,2,3};
        int i = largestRectangleArea(ints);
        System.out.println(i);
    }

    /**
     * 对于 i 分别从从左边、右边寻找比它低的元素、然后记录`宽度 = right - left` ,最后`面积 = 宽度 * 高度`
     * 数据结构：寻找比我大、小的元素，这种题型可以使用栈，只需O(1)的时间复杂度
     * @param heights
     * @return
     */
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int len = heights.length;
        int[] lefts = new int[len];
        int[] rights = new int[len];

        for (int i = 0; i < len; i++) {//寻找左边第一个比我小的元素
            int te = heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] >= te){//递增栈
                stack.pop();
            }
            if (!stack.isEmpty()){
                lefts[i] = stack.peek();
            }else {
                lefts[i] = -1;
            }
            stack.push(i);
        }
        stack.clear();//清空
        for (int i = len - 1; i >= 0; i--) {//寻找右边第一个比我小的元素
            int te = heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] >= te){//递增栈
                stack.pop();
            }
            if (!stack.isEmpty()){
                rights[i] = stack.peek();
            }else {
                rights[i] = len;
            }
            stack.push(i);
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            int left = lefts[i];
            int right = rights[i];
            ans = Math.max(ans, (right - left - 1) * heights[i]);
        }
        return ans;
    }
    public int largestRectangleArea2(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);

        Stack<Integer> mono_stack = new Stack<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }


}
